/*
 * @lc app=leetcode.cn id=327 lang=javascript
 *
 * [327] 区间和的个数
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */
var merge = function(arr, l, r, lower, upper){
  if(l >= r) return 0;

  let mid = (l + r) >> 1;
  let result = 0;
  result += merge(arr, l ,mid, lower, upper)
  result += merge(arr, mid + 1 ,r, lower, upper);

  // 统计横跨的数量 
  let i = l, left = mid +1, right = mid + 1;
  while(i <= mid) {
    while(left<=r && arr[left] - arr[i] < lower) left++; // 右 - i >= lower边界
    while(right<=r && arr[right] -arr[i] <= upper) right++; // 右 - i <= upper 边界
    result += (right-left);
    i++;
  }

  // 随后合并两个排序数组 
  const sorted = new Array(r - l + 1); 
  let p1 = l, p2 = mid + 1;
  let p = 0; 
  while (p1 <= mid || p2 <= r) { 
    if (p1 > mid) { 
      sorted[p++] = arr[p2++]; 
    } else if (p2 > r) { 
      sorted[p++] = arr[p1++]; 
    } else { 
      if (arr[p1] < arr[p2]) { 
        sorted[p++] = arr[p1++]; 
      } else { 
        sorted[p++] = arr[p2++]; 
      } 
    } 
  } 
  for (let i = 0; i < sorted.length; i++) { 
    arr[l + i] = sorted[i]; 
  }
  return result;
}
var countRangeSum = function(nums, lower, upper) {
  var sumA = [0];
  nums.reduce((res, pre)=>{
    sumA.push(res + pre);
    return res + pre;
  }, 0)
  return merge(sumA, 0, sumA.length - 1, lower, upper)
 
};
// @lc code=end

